package com.leetcode.根据算法进行分类.滑动窗口相关;

/**
 * @author: ZhouBert
 * @date: 2021/2/5
 * @description: 1208. 尽可能使字符串相等
 * https://leetcode-cn.com/problems/get-equal-substrings-within-budget/
 * 写代码的时候，不要马上就想着一蹴而就，++ -- 都用上，而是都写完以后，再用 ++ -- 简化。
 */
public class B_1208_尽可能使字符串相等 {

	public static void main(String[] args) {
		B_1208_尽可能使字符串相等 action = new B_1208_尽可能使字符串相等();
		test1(action);
		test2(action);
		test3(action);
		test4(action);
		test5(action);
	}

	public static void test1(B_1208_尽可能使字符串相等 action) {
		//3
		String s = "abcd";
		String t = "bcdf";
		int maxCost = 3;
		int res = action.equalSubstring(s, t, maxCost);
		System.out.println("res = " + res);
	}

	public static void test2(B_1208_尽可能使字符串相等 action) {
		//1
		String s = "abcd";
		String t = "cdef";
		int maxCost = 3;
		int res = action.equalSubstring(s, t, maxCost);
		System.out.println("res = " + res);
	}

	public static void test3(B_1208_尽可能使字符串相等 action) {
		//1
		String s = "abcd";
		String t = "acde";
		int maxCost = 0;
		int res = action.equalSubstring(s, t, maxCost);
		System.out.println("res = " + res);
	}

	public static void test4(B_1208_尽可能使字符串相等 action) {
		//1
		String s = "anryddgaqpjdw";
		String t = "zjhotgdlmadcf";
		int maxCost = 5;
		int res = action.equalSubstring(s, t, maxCost);
		System.out.println("res = " + res);
	}

	public static void test5(B_1208_尽可能使字符串相等 action) {
		//4
		String s = "krpgjbjjznpzdfy";
		String t = "nxargkbydxmsgby";
		int maxCost = 14;
		int res = action.equalSubstring(s, t, maxCost);
		System.out.println("res = " + res);
	}


	/**
	 * 这个确实适合做滑动窗口
	 * --
	 * 官方题解的滑动窗口更容易理解
	 * @param s
	 * @param t
	 * @param maxCost
	 * @return
	 */
	public int equalSubstring(String s, String t, int maxCost) {
		//1.边界判断
		int res = 0;
		if (s == null || t == null) {
			return res;
		}
		int len = s.length();
		if (len == 0) {
			return res;
		}
		//2.生成 costArr
		int[] costArr = new int[len];
		char[] sChars = s.toCharArray();
		char[] tChars = t.toCharArray();
		for (int i = 0; i < len; i++) {
			costArr[i] = Math.abs(sChars[i] - tChars[i]);
		}
		//3.进行滑动窗口（滑动只是一个框架，具体在滑动中如何变动需要随机应变，因地制宜）
		int begin = 0, end = 1;
		int cost = costArr[0];
		while (end < len) {
			while (end < len && cost <= maxCost) {
				cost += costArr[end++];
			}

			res = Math.max(res, end - begin - 1);
			if (end == len) {
				break;
			}

			//此时 end 是属于超标的
			cost -= costArr[begin++];
			cost += costArr[end++];
		}
		if (end==len){
			if (cost <= maxCost){
				res = Math.max(res, end - begin);
			}
		}
		return res;
	}
}
